package codetop.microsoft.T72;

import util.ListUtil;

/**
 * @Author: 18362
 * @Create: 2022-08-14 13:52:34 星期日
 */
class Solution {
    public int minDistance(String word1, String word2) {
        int[] dp = new int[word2.length() + 1];
        for (int i=1; i<dp.length; ++i)
            dp[i] = i;
        for (int i=1; i<word1.length()+1; ++i) {
            int last = dp[0];
            dp[0] = i;
            for (int j=1; j<dp.length; ++j) {
                int temp = dp[j];
                if (word1.charAt(i-1) == word2.charAt(j-1))
                    dp[j] = last;
                else
                    dp[j] = Math.min(dp[j-1], Math.min(dp[j], last)) + 1;
                last = temp;
            }
        }
        return dp[dp.length-1];
    }
}